package offer.day7;

import java.util.Scanner;

public class No10Second_fibonacciFrog {
    /*
     * 面试题10：
     * 	题目2：一只青蛙一次可以跳上1级台阶，也可以跳上2级台阶。
     * 求该青蛙跳上一个n级台阶总共有多少种跳法。
     *
     * 思路：可以将n级台阶跳法问题看成是n的函数，记为f(n)
     * 		当n>2时，第一次跳的时候就有两种选择：
     * 		1.第一次跳1级，则剩下n-1级台阶，记为f(n-1)
     * 		2.第一次跳2级，则剩下n-2级台阶，记为f(n-2)
     * 		即 f(n) = f(n-1) + f(n-2)
     *
     * 使用斐波那契思想，解青蛙跳台阶问题
     *
     * */
    public static void main(String[] args) {
        No10First_fibonacci admin = new No10First_fibonacci();
        Scanner n = new Scanner(System.in);
        System.out.println("输入青蛙跳到第几级：");
        int i = n.nextInt();
        System.out.println("青蛙调到第"+i+"级台阶一共有"+admin.fibonacci(i)+"种跳法");
    }

    public int fibonacci(int n){
        int result=0;
        int preTwo=1;
        int preOne=0;
        if(n==0) return 0;
        if(n==1) return 1;
        for(int i=2;i<=n;i++){
            result=preOne+preTwo;
            preOne=preTwo;
            preTwo=result;
        }
        return result;
    }
}
